Secure communication and authorization is a highly important topic these days. Many secure communication and authorization schemes rely on cryptographic systems and methods. In classical cryptography, the mathematically (still not entirely proven) fact is used that some mathematical functions can be calculated without difficulty in one direction, but solving the inverse mathematical problem practically impossible; this would at least require extremely high and time-consuming computational efforts. These computational efforts will, however, suddenly be significantly reduced when the first quantum computers start operation. One is therefore looking for other approaches which are inherently secure. One approach is quantum cryptography which is basically a physical approach relying on the fact that each measurement influences unknown quantum states, and that it is therefore in principle possible to find out about an eavesdropper. Quantum states are, however, rather fragile states, and it is to date hard to prepare and handle them appropriately, in particular over larger distances.
In practical cryptography, a physically unclonable function or PUF [1,2] is a function that is embodied in a physical structure which is easy to evaluate, but which is hard to predict and which is assumed to be physically unclonable because of a strong dependence on uncontrollable aspects of the manufacturing process. PUFs have a unique challenge-response behavior. They are of interest as a means of authentication for these reasons.
A PUF owner should typically prove access to a secret by presenting his PUF to a verifying party. The verifying party sends a signal called challenge to the PUF, and the PUF then creates a unique and hard to predict reply signal called response. This response is supplied back to the verifying party so that it can be verified that the PUF owner actually has authorized access to the secret or resource.
Many PUF-like systems have previously been described. These include: optical PUFs [Pappu, R.: Physical One-Way Functions. PhD thesis, MIT (2001); Pappu, R., Recht, B., Taylor, J., Gershenfeld, N., Physical One-Way Functions, Science 297, pp. 2026-2030 (2002)], delays in integrated circuits [Gassend, B., Clarke, D. E., van Dijk, M., Devadas, S., Silicon physical unknown functions, ACM Conf. on Computer and Communications Security-CCS 2002, November 2002, pp. 148-160 (2002)], dielectric properties of security coatings [Tuyls, P., Schrijen, G. J., {hacek over (S)}korić, B., van Geloven, J., Verhaegh, R., Wolters, R., Read-proof hardware from protective coatings, Goubin, L., Matsui, M. (eds.), CHES 2006. LNCS, Vol. 4249, pp. 369-383, Springer, Heidelberg (2006)], two-dimensional fiber-optic configurations [Kirovski, D., Toward an automated verification of certificates of authenticity, ACM Conference on Electronic Commerce, pp. 160-169. ACM, New York (2004)], radiofrequent probing of wire configurations [DeJean, G., Kirovski, D., Radio frequency certificates of authenticity, IEEE Antenna and Propagation Symposium-URSI (2006)] and thin-film resonators [{hacek over (S)}korić, B., Bel, T., Blom, A. H. M., de Jong, B. R., Kretschman, H., Nellissen, A. J. M., Randomized resonators as uniquely identifiable anti-counterfeiting tags, Secure Component and System Identification Workshop, Berlin (March 2008)], laser probing of fibers in paper [Buchanan, J. D. R., Cowburn, R. P., Jausovec, A., Petit, D., Seem, P., Xiong, G., Atkinson, D., Fenton, K., Allwood, D.A., Bryan, M. T., Forgery: ‘fingerprinting’ documents and packaging, Nature, Brief Communications 436, pg. 475 (2005)], startup values of SRAM cells [Guajardo, J., Kumar, S. S., Schrijen, G. J., Tuyls, P., FPGA intrinsic PUFs and their use for IP protection, Paillier, P., Verbauwhede, I. (eds.), CHES 2007, LNCS, Vol. 4727, pp. 63-80, Springer, Heidelberg (2007)], butterfly PUFs [Kumar, S. S., Guajardo, J., Maes, R., Schrijen, G. J., Tuyls, P., The Butterfly PUF: Protecting IP on every FPGA, HOST 2008, pp. 67-70, IEEE, Los Alamitos (2008)], phosphor patterns [Chong, C. N., Jiang, D., Zhang, J., Guo, L., Anti-counterfeiting with a random pattern, SECURWARE 2008, pp. 146-153, IEEE, Los Alamitos (2008)], and phase-change memory states [Kursawe, K., Sadeghi, A.-R., Schellekens, D., {hacek over (S)}korić, B., Tuyls, P., Reconfigurable physical unclonable functions, HOST 2009 (2009)].
WO 2007/046018 A1 describes an optical PUF with a combined sensor and display. It applies light which is scattered by a light scattering element comprising a transmissive material which contains randomly distributed light scattering particles which scatter incident light so that a random speckle pattern is created and spread over light detecting elements. The key idea of WO 2007/046018 A1 is to include reflecting picture elements into the device so that it becomes possible to modify applied challenges by activating and switching off the picture elements, thereby also modifying the corresponding response/speckle pattern.
US 2006/0095773 A1 describes an authentication system, a light emitting device, authentication device, and an authentication method which applies an emission-angle dependent light emitting device and a corresponding emission-angle dependent light detector.
WO 2005/059629 A1 describes an optical method and an apparatus for detection of a speckle based PUF and focuses on the definition of criteria employed to determine the size of pixels of a detector that will give rise to detection of all relevant bits (i.e., the pixels are small enough) without too much redundancy (i.e., the pixels are large enough).
US 2008/0121708 A1 describes physical credentials and related methods. Directional albedo of an article is measured and stored. When the article is later presented, it can be confirmed to be the same particular article by re-measuring the albedo function, and checking for correspondence against earlier stored data. The disclosed device and method gains its security from statistics considerations. The disclosed device and method is not, however, inherently secure, in particular not quantum secure.
US 2007/046018 A1 describes an integrated physical unclonable function (PUF) with a combined sensor and display. A specific creation of challenge response pairs is disclosed. Quantum security is not, however, achieved.
WO 98/28707 describes a method and an apparatus for enhancing the integrity of visual authentication. The illumination of an object is modulated for hindering attacks by replaying recorded images. The object is no PUF. Quantum security is no topic.
The security of the verification in all existing PUFs relies on the fact that the validator knows he is probing the properties of a physical entity such as an integrated circuit, a SRAM cell, a phosphor layer, etc. If the PUF owner doesn't trust the validator, the PUF owner will not want to give away his PUF for checking. The best a validator can therefore do is to try to check from a (possibly small) distance, in which case he can be fooled by an intelligent attacker system emulating the PUF. Highly desired for the authentication processes is a secure and practical authentication protocol which does not rely on a trusted remote reader device or on examining the PUF to make sure it is a physical object of the expected size, weight and complexity.
A possible direction was recently described by B. {hacek over (S)}korić in a mathematical abstract paper [{hacek over (S)}korić, B., Quantum Readout of Physical Unclonable Functions, AFRICACRYPT 2010, LNCS 6055, pp. 369-386 (2010)] who suggested a quantum secure readout of a classical PUF that is challenged using a quantum state, and who's response is also a quantum state. The protocol allows for authenticating a QR-PUF remotely without reliance on a trusted remote reader device. The paper by B. {hacek over (S)}korić did not suggest a physical implementation and suffers from the fact that its security proof uses (necessarily fragile) quantum states as key element.